package com.zhupf.Backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhupf
 * @date 2024年01月02日 9:41
 * @Description
 *
 * 131. 分割回文串
 */
public class Partition {

    private static List<List<String>> ans;

    public static void main(String[] args) {
        partition("aab");
    }

    public static List<List<String>> partition(String s) {
         ans = new ArrayList<>();
        List<String> res = new ArrayList<>();
        dfs(s,res,0);
        return ans;
    }

    private static void dfs(String s,List<String> res,int idx){
        if(idx>s.length()-1){
            ans.add(new ArrayList<>(res));
        }
        for (int i = idx;i < s.length() ; i ++){
            String item = s.substring(idx,i+1);
            if(isRircle(item)){
                res.add(item);
                dfs(s,res,i+1);
                res.remove(res.size()-1);
            }
        }
    }

    private static boolean isRircle(String s){
        if (s == null || s.length() == 0) {
            return true;
        }
        int first = 0, last = s.length() - 1;
        while (first < last) {
            if (s.charAt(first) != s.charAt(last)) {
                return false;
            }
            first++;
            last--;
        }
        return true;
    }

}
